package binaryTree;

/**堆排序*/
public class HeapSort {

	public static <AnyType extends Comparable<? super AnyType>> void heapsort(AnyType[] a){
		//创建堆
		for(int i=a.length/2;i>=0;i--){
			percDown(a,i,a.length);
		}
		//删除最大元素
		int p=1;
		for(int i=a.length-1;i>0;i--){
			swapReferences(a,0,i);
			percDown(a,0,i);
		}
	}
	//下滤
	private static <AnyType extends Comparable<? super AnyType>> void percDown(AnyType[] a,int i,int n){
		int child;
		AnyType tmp;
		
		for(tmp=a[i];leftChild(i)<n;i=child){
			child = leftChild(i);
			if(child != n-1 && a[child].compareTo(a[child+1])<0 ){
				child++;
			}
			if(tmp.compareTo(a[child])<0){
				a[i]=a[child];
			}else{
				break;
			}
		}
		a[i]=tmp;
	}
	//
	private static int leftChild(int i){
		return 2*i+1;
	}
	//交换元素
	private static <AnyType> void swapReferences(AnyType[] a,int n,int m){
		AnyType tmp;
		tmp=a[n];
		a[n]=a[m];
		a[m]=tmp;
	}
	
//	
//	public static void main(String[] args) {
//		int n=0;
//		HeapSort s=new HeapSort();
//		Scanner in = new Scanner(System.in);
//		System.out.println("请输入要排序数组的大小：");//8
//		n=in.nextInt();
//		Integer quick[] = new Integer[n];
//		System.out.println("请输入数组中的元素");
//		//12 45 21 12 30 2 68 33
//		for(int i=0;i<n;i++){
//			quick[i]=in.nextInt();
//		}
//		s.heapsort(quick);
//		System.out.println("排序的最后结果为：");
//		for(int j=0;j<quick.length;j++){
//			System.out.print(quick[j]+"\t");
//		}
//		
//	}
}
